﻿ #include <stdlib.h>

//选择类排序

/*
* 简单选择排序
* 1.依次从无序序列选择最小元素
* 2.将最小元素与无序序列的第一个元素互换
* 
* 时间复杂度：最好O(n)，最坏/平均O(n²)
*/
void SimpleSelectSort(int A[],int n) {
	int tmp, min;
	for (int i = 0; i < n-1; i++) //n-1趟循环
	{
		min = i;//无序序列最小元素
		for (int j = i+1; j < n; j++)
		{
			if (A[j] < A[min]) {
				min = j;
			}
		}
		if (min != i) {
			//交换最小值
			tmp = A[i];
			A[i] = A[min];
			A[min] = tmp;
		}
	}
}

/*
* 堆排序
* 1.建立大根堆（小根堆） O(n)
* 2.基于大根堆，进行选择排序 O(nlog2n)
* 
*/

//建立大根堆：A[]是完全二叉树的顺序存储，1.从内存结点由大到小，不断调整结点对应的子树为大根堆 2.对每一个内部结点调整时,把根的值与子节点的最大值比较交换，对交换后的子树同样的过程判断
void CreateMaxHeap(int A[],int len) {
	//从完全二叉树的内部结点，由大到小，调整子树大根堆
	for (int i = len /2; i > 0; --i)
	{
		HeapAdjust(A,i, len);
	}
}

//以k为根的子树调整为大根堆
void HeapAdjust(int A[], int k, int len) {
	A[0] = A[k];//A[0]不存元素，暂存当前子树的根结点k的值
	for (int i = 2*k; i <= len; i*=2)//这里i每次循环取k的左子结点
	{
		//找出左右子结点的最大值
		if (i < len && A[i] < A[i + 1]) {
			i++;//i指向较大的结点
		}
		if (A[0] >= A[i]) {
			break;
		}
		else {
			A[k] = A[i];//先把根结点的值替换为，其子节点的较大值（已确定为大根值）
			k = i;//k指向子节点i的位置，下一轮同样判断i为根的子树
		}
	}
	A[k] = A[0];//若未发生交换k不变；若发生交换，退出循环时k指向其交换的子节点。A[0]的值下坠

}

//基于大根堆，进行选择排序：1.每次选择堆顶元素与堆底元素互换 2.堆顶元素加入排序序列（排除大根堆外）3.对交换后的大根堆进行调整后，进行下一轮；直到堆内只有一个元素为止（n-1趟）。大根堆的排序是递增序列
void HeapSort(int A[],int len) {
	CreateMaxHeap(A, len);
	//A已经调整后大根堆后的顺序存储,此时A中元素顺序和完全二叉树的层序遍历顺序相同
	for (int i = len; i > 1; i--)//len-1轮
	{
		//大根堆第一个元素与最后一个元素交换
		A[0] = A[1];
		A[1] = A[i];
		A[i] = A[0];
		HeapAdjust(A, 1, i - 1);//注意这里i-1，根换到后面已排序，排除在前面的大根堆之外
	}
}
